from typing import List


class Solution:
    _MIN, _MAX = -10 ** 9, 10 ** 9
    _TIMES = 50  # 迭代次数

    def minRecSize(self, lines: List[List[int]]) -> float:
        if len(lines) == 1:
            return 0
        if len(set(k for k, b in lines)) == 1:
            return 0

        lines.sort(key=lambda x: (x[0], x[1]))

        # 寻找最右侧的交点
        left, right = self._MIN, self._MAX
        for _ in range(self._TIMES):
            mid = (left + right) / 2

            smaller = False
            last = -float("inf")
            for k, b in lines:
                now = k * mid + b
                if now < last:
                    smaller = True
                    break
                else:
                    last = now

            if smaller:
                left = mid
            else:
                right = mid

        max_right = (left + right) / 2

        # 寻找最上侧的交点
        left, right = self._MIN, self._MAX
        for _ in range(self._TIMES):
            mid = (left + right) / 2

            smaller = False
            last = float("inf")
            for k, b in lines:
                now = (mid - b) / k
                if now > last:
                    smaller = True
                    break
                else:
                    last = now

            if smaller:
                left = mid
            else:
                right = mid

        max_top = (left + right) / 2

        # 左侧和右侧时，斜率的影响是不一样的
        lines.sort(key=lambda x: (x[0], -x[1]))

        # 寻找最左侧的交点
        left, right = self._MIN, self._MAX
        for _ in range(self._TIMES):
            mid = (left + right) / 2

            bigger = False
            last = float("inf")
            for k, b in lines:
                now = k * mid + b
                if now > last:
                    bigger = True
                    break
                else:
                    last = now

            if bigger:
                right = mid
            else:
                left = mid

        max_left = (left + right) / 2

        # 寻找最下侧的交点
        left, right = self._MIN, self._MAX
        for _ in range(self._TIMES):
            mid = (left + right) / 2

            smaller = False
            last = -float("inf")
            for k, b in lines:
                now = (mid - b) / k
                if now < last:
                    smaller = True
                    break
                else:
                    last = now

            if smaller:
                right = mid
            else:
                left = mid

        max_bottom = (left + right) / 2

        # print("L", max_left, "R", max_right, "B", max_bottom, "T", max_top)

        return (max_top - max_bottom) * (max_right - max_left)


if __name__ == "__main__":
    print(Solution().minRecSize(lines=[[2, 3], [3, 0], [4, 1]]))  # 48
    print(Solution().minRecSize(lines=[[1, 1], [2, 3]]))  # 0

    # 测试用例6/49
    print(Solution().minRecSize(lines=[[1, 1]]))  # 0

    # 测试用例7/49
    print(Solution().minRecSize(lines=[[5, 2], [5, -4], [2, -5], [4, -1], [2, 0]]))  # 144

    # 测试用例48/49
    print(Solution().minRecSize(lines=[[1, 1], [1, 7], [1, 17]]))  # 0
